package likou;

import java.util.Arrays;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/06/06 07:43
 */
public class _474 {
    public static void main(String[] args) {
        System.out.println(findMaxForm(new String[]{"10", "0001", "111001", "1", "0"}, 3, 4));
    }

    static int max = 0;

    public static int findMaxForm(String[] strs, int m, int n) {
        int[][] nums = new int[strs.length][2];
        for (int i = 0; i < strs.length; i++) {
            int length = strs[i].length();
            int n1 = strs[i].replace("0", "").length();
            int n0 = length - n1;
            nums[i][0] = n0;
            nums[i][1] = n1;
        }
        Arrays.sort(nums, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i][0] <= m && nums[i][1] <= n) {
                dfs(i, nums, m, n, nums[i][0], nums[i][1], 1);
            }
        }
        return max;
    }

    public static void dfs(int start, int[][] nums, int m, int n, int nowM, int nowN, int num) {
        if (start >= nums.length) {
            return;
        }
        if (nowM == m && nowN == n) {
            max = Math.max(max, num);
            return;
        }
        for (int i = start + 1; i < nums.length; i++) {
            if (nowM + nums[i][0] <= m && nowN + nums[i][1] <= n) {
                dfs(i, nums, m, n, nowM + nums[i][0], nowN + nums[i][1], num + 1);
            }
        }
    }
}
